home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / source.exe / POSIX / GREP / REGEXP.C < prev    next >
C/C++ Source or Header  |  1992-09-30  |  31KB  |  1,331 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  *    This version has alterations for ISO C usage. These changes are
  22.  *    Copyright 1992 DataFocus Incorporated. All rights reserved.
  23.  *
  24.  * Beware that some of this code is subtly aware of the way operator
  25.  * precedence is structured in regular expressions.  Serious changes in
  26.  * regular-expression syntax might require a total rethink.
  27.  */
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. #include "regexp.h"
  32. #include "regmagic.h"
  33.  
  34. /*
  35.  * The "internal use only" fields in regexp.h are present to pass info from
  36.  * compile to execute that permits the execute phase to run lots faster on
  37.  * simple cases.  They are:
  38.  *
  39.  * regstart    char that must begin a match; '\0' if none obvious
  40.  * reganch    is the match anchored (at beginning-of-line only)?
  41.  * regmust    string (pointer into program) that match must include, or NULL
  42.  * regmlen    length of regmust string
  43.  *
  44.  * Regstart and reganch permit very fast decisions on suitable starting points
  45.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  46.  * of lines that cannot possibly match.  The regmust tests are costly enough
  47.  * that regcomp() supplies a regmust only if the r.e. contains something
  48.  * potentially expensive (at present, the only such thing detected is * or +
  49.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  50.  * supplied because the test in regexec() needs it and regcomp() is computing
  51.  * it anyway.
  52.  */
  53.  
  54. /*
  55.  * Structure for regexp "program".  This is essentially a linear encoding
  56.  * of a nondeterministic finite-state machine (aka syntax charts or
  57.  * "railroad normal form" in parsing technology).  Each node is an opcode
  58.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  59.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  60.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  61.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  62.  * opposed to a collection of them) is never concatenated with anything
  63.  * because of operator precedence.)  The operand of some types of node is
  64.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  65.  * particular, the operand of a BRANCH node is the first node of the branch.
  66.  * (NB this is *not* a tree structure:  the tail of the branch connects
  67.  * to the thing following the set of BRANCHes.)  The opcodes are:
  68.  */
  69.  
  70. /* definition    number    opnd?    meaning */
  71. #define    END    0    /* no    End of program. */
  72. #define    BOL    1    /* no    Match "" at beginning of line. */
  73. #define    EOL    2    /* no    Match "" at end of line. */
  74. #define    ANY    3    /* no    Match any one character. */
  75. #define    ANYOF    4    /* str    Match any character in this string. */
  76. #define    ANYBUT    5    /* str    Match any character not in this string. */
  77. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  78. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  79. #define    EXACTLY    8    /* str    Match this string. */
  80. #define    NOTHING    9    /* no    Match empty string. */
  81. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  82. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  83. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  84.             /*    OPEN+1 is number 1, etc. */
  85. #define    CLOSE    30    /* no    Analogous to OPEN. */
  86.  
  87. /*
  88.  * Opcode notes:
  89.  *
  90.  * BRANCH    The set of branches constituting a single choice are hooked
  91.  *        together with their "next" pointers, since precedence prevents
  92.  *        anything being concatenated to any individual branch.  The
  93.  *        "next" pointer of the last BRANCH in a choice points to the
  94.  *        thing following the whole choice.  This is also where the
  95.  *        final "next" pointer of each individual branch points; each
  96.  *        branch starts with the operand node of a BRANCH node.
  97.  *
  98.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  99.  *        exists to make loop structures possible.
  100.  *
  101.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  102.  *        BRANCH structures using BACK.  Simple cases (one character
  103.  *        per match) are implemented with STAR and PLUS for speed
  104.  *        and to minimize recursive plunges.
  105.  *
  106.  * OPEN,CLOSE    ...are numbered at compile time.
  107.  */
  108.  
  109. /*
  110.  * A node is one char of opcode followed by two chars of "next" pointer.
  111.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  112.  * value is a positive offset from the opcode of the node containing it.
  113.  * An operand, if any, simply follows the node.  (Note that much of the
  114.  * code generation knows about this implicit relationship.)
  115.  *
  116.  * Using two bytes for the "next" pointer is vast overkill for most things,
  117.  * but allows patterns to get big without disasters.
  118.  */
  119. #define    OP(p)    (*(p))
  120. #if 0
  121. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + *((p)+2)&0377)
  122. #else
  123. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  124. #endif
  125. #define    OPERAND(p)    ((p) + 3)
  126.  
  127. /*
  128.  * See regmagic.h for one further detail of program structure.
  129.  */
  130.  
  131.  
  132. /*
  133.  * Utility definitions.
  134.  */
  135. #ifndef CHARBITS
  136. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  137. #else
  138. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  139. #endif
  140.  
  141. #define    FAIL(m)    { regerror(m); return(NULL); }
  142. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  143. #define    META    "^$.[()|?+*\\"
  144.  
  145. /*
  146.  * Flags to be passed up and down.
  147.  */
  148. #define    HASWIDTH    01    /* Known never to match null string. */
  149. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  150. #define    SPSTART        04    /* Starts with * or +. */
  151. #define    WORST        0    /* Worst case. */
  152.  
  153. /*
  154.  * Global work variables for regcomp().
  155.  */
  156. static char *regparse;        /* Input-scan pointer. */
  157. static int regnpar;        /* () count. */
  158. static char regdummy;
  159. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  160. static long regsize;        /* Code size. */
  161.  
  162. /*
  163.  * Forward declarations for regcomp()'s friends.
  164.  */
  165. #ifndef STATIC
  166. #define    STATIC    static
  167. #endif
  168. #if __STDC__
  169. STATIC char *reg (int, int *);
  170. STATIC char *regbranch (int *);
  171. STATIC char *regpiece (int *);
  172. STATIC char *regatom (int *);
  173. STATIC char *regnode (char);
  174. STATIC void regc (char);
  175. STATIC void reginsert (char, char *);
  176. STATIC void regtail (char *, char *);
  177. STATIC void regoptail (char *, char *);
  178. STATIC char *regnext (register char *);
  179. #else
  180. STATIC char *reg();
  181. STATIC char *regbranch();
  182. STATIC char *regpiece();
  183. STATIC char *regatom();
  184. STATIC char *regnode();
  185. STATIC char *regnext();
  186. STATIC void regc();
  187. STATIC void reginsert();
  188. STATIC void regtail();
  189. STATIC void regoptail();
  190. # ifdef STRCSPN
  191. STATIC int strcspn();
  192. # endif
  193. #endif
  194.  
  195. /*
  196.  - regcomp - compile a regular expression into internal code
  197.  *
  198.  * We can't allocate space until we know how big the compiled form will be,
  199.  * but we can't compile it (and thus know how big it is) until we've got a
  200.  * place to put the code.  So we cheat:  we compile it twice, once with code
  201.  * generation turned off and size counting turned on, and once "for real".
  202.  * This also means that we don't allocate space until we are sure that the
  203.  * thing really will compile successfully, and we never have to move the
  204.  * code and thus invalidate pointers into it.  (Note that it has to be in
  205.  * one piece because free() must be able to free it all.)
  206.  *
  207.  * Beware that the optimization-preparation code in here knows about some
  208.  * of the structure of the compiled regexp.
  209.  */
  210. regexp *
  211. #if __STDC__
  212. regcomp (char *exp)
  213. #else
  214. regcomp(exp)
  215. char *exp;
  216. #endif
  217. {
  218.     register regexp *r;
  219.     register char *scan;
  220.     register char *longest;
  221.     register int len;
  222.     int flags;
  223. #if !__STDC__
  224.     extern char *malloc();
  225. #endif
  226.  
  227.     if (exp == NULL)
  228.         FAIL("NULL argument");
  229.  
  230.     /* First pass: determine size, legality. */
  231.     regparse = exp;
  232.     regnpar = 1;
  233.     regsize = 0L;
  234.     regcode = ®dummy;
  235.     regc(MAGIC);
  236.     if (reg(0, &flags) == NULL)
  237.         return(NULL);
  238.  
  239.     /* Small enough for pointer-storage convention? */
  240.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  241.         FAIL("regexp too big");
  242.  
  243.     /* Allocate space. */
  244.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  245.     if (r == NULL)
  246.         FAIL("out of space");
  247.  
  248.     /* Second pass: emit code. */
  249.     regparse = exp;
  250.     regnpar = 1;
  251.     regcode = r->program;
  252.     regc(MAGIC);
  253.     if (reg(0, &flags) == NULL)
  254.         return(NULL);
  255.  
  256.     /* Dig out information for optimizations. */
  257.     r->regstart = '\0';    /* Worst-case defaults. */
  258.     r->reganch = 0;
  259.     r->regmust = NULL;
  260.     r->regmlen = 0;
  261.     scan = r->program+1;            /* First BRANCH. */
  262.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  263.         scan = OPERAND(scan);
  264.  
  265.         /* Starting-point info. */
  266.         if (OP(scan) == EXACTLY)
  267.             r->regstart = *OPERAND(scan);
  268.         else if (OP(scan) == BOL)
  269.             r->reganch++;
  270.  
  271.         /*
  272.          * If there's something expensive in the r.e., find the
  273.          * longest literal string that must appear and make it the
  274.          * regmust.  Resolve ties in favor of later strings, since
  275.          * the regstart check works with the beginning of the r.e.
  276.          * and avoiding duplication strengthens checking.  Not a
  277.          * strong reason, but sufficient in the absence of others.
  278.          */
  279.         if (flags&SPSTART) {
  280.             longest = NULL;
  281.             len = 0;
  282.             for (; scan != NULL; scan = regnext(scan))
  283. #if __STDC__
  284.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= (size_t) len) {
  285.                     longest = OPERAND(scan);
  286.                     len = strlen(OPERAND(scan));
  287.                 }
  288. #else
  289.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  290.                     longest = OPERAND(scan);
  291.                     len = (int) strlen(OPERAND(scan));
  292.                 }
  293. #endif
  294.             r->regmust = longest;
  295.             r->regmlen = len;
  296.         }
  297.     }
  298.  
  299.     return(r);
  300. }
  301.  
  302. /*
  303.  - reg - regular expression, i.e. main body or parenthesized thing
  304.  *
  305.  * Caller must absorb opening parenthesis.
  306.  *
  307.  * Combining parenthesis handling with the base level of regular expression
  308.  * is a trifle forced, but the need to tie the tails of the branches to what
  309.  * follows makes it hard to avoid.
  310.  */
  311. STATIC char *
  312. #if __STDC__
  313. reg (int paren, int *flagp)
  314. #else
  315. reg(paren, flagp)
  316. int paren;            /* Parenthesized? */
  317. int *flagp;
  318. #endif
  319. {
  320.     register char *ret;
  321.     register char *br;
  322.     register char *ender;
  323.     register int parno;
  324.     int flags;
  325.  
  326.     *flagp = HASWIDTH;    /* Tentatively. */
  327.  
  328.     /* Make an OPEN node, if parenthesized. */
  329.     if (paren) {
  330.         if (regnpar >= NSUBEXP)
  331.             FAIL("too many ()");
  332.         parno = regnpar;
  333.         regnpar++;
  334.         ret = regnode((char) (OPEN+parno));
  335.     } else
  336.         ret = NULL;
  337.  
  338.     /* Pick up the branches, linking them together. */
  339.     br = regbranch(&flags);
  340.     if (br == NULL)
  341.         return(NULL);
  342.     if (ret != NULL)
  343.         regtail(ret, br);    /* OPEN -> first. */
  344.     else
  345.         ret = br;
  346.     if (!(flags&HASWIDTH))
  347.         *flagp &= ~HASWIDTH;
  348.     *flagp |= flags&SPSTART;
  349.     while (*regparse == '|') {
  350.         regparse++;
  351.         br = regbranch(&flags);
  352.         if (br == NULL)
  353.             return(NULL);
  354.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  355.         if (!(flags&HASWIDTH))
  356.             *flagp &= ~HASWIDTH;
  357.         *flagp |= flags&SPSTART;
  358.     }
  359.  
  360.     /* Make a closing node, and hook it on the end. */
  361.     ender = regnode((char)((paren) ? CLOSE+parno : END));    
  362.     regtail(ret, ender);
  363.  
  364.     /* Hook the tails of the branches to the closing node. */
  365.     for (br = ret; br != NULL; br = regnext(br))
  366.         regoptail(br, ender);
  367.  
  368.     /* Check for proper termination. */
  369.     if (paren && *regparse++ != ')') {
  370.         FAIL("unmatched ()");
  371.     } else if (!paren && *regparse != '\0') {
  372.         if (*regparse == ')') {
  373.             FAIL("unmatched ()");
  374.         } else
  375.             FAIL("junk on end");    /* "Can't happen". */
  376.         /* NOTREACHED */
  377.     }
  378.  
  379.     return(ret);
  380. }
  381.  
  382. /*
  383.  - regbranch - one alternative of an | operator
  384.  *
  385.  * Implements the concatenation operator.
  386.  */
  387. STATIC char *
  388. #if __STDC__
  389. regbranch (int *flagp)
  390. #else
  391. regbranch(flagp)
  392. int *flagp;
  393. #endif
  394. {
  395.     register char *ret;
  396.     register char *chain;
  397.     register char *latest;
  398.     int flags;
  399.  
  400.     *flagp = WORST;        /* Tentatively. */
  401.  
  402.     ret = regnode(BRANCH);
  403.     chain = NULL;
  404.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  405.         latest = regpiece(&flags);
  406.         if (latest == NULL)
  407.             return(NULL);
  408.         *flagp |= flags&HASWIDTH;
  409.         if (chain == NULL)    /* First piece. */
  410.             *flagp |= flags&SPSTART;
  411.         else
  412.             regtail(chain, latest);
  413.         chain = latest;
  414.     }
  415.     if (chain == NULL)    /* Loop ran zero times. */
  416.         (void) regnode(NOTHING);
  417.  
  418.     return(ret);
  419. }
  420.  
  421. /*
  422.  - regpiece - something followed by possible [*+?]
  423.  *
  424.  * Note that the branching code sequences used for ? and the general cases
  425.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  426.  * both the endmarker for their branch list and the body of the last branch.
  427.  * It might seem that this node could be dispensed with entirely, but the
  428.  * endmarker role is not redundant.
  429.  */
  430. STATIC char *
  431. #if __STDC__
  432. regpiece (int *flagp)
  433. #else
  434. regpiece(flagp)
  435. int *flagp;
  436. #endif
  437. {
  438.     register char *ret;
  439.     register char op;
  440.     register char *next;
  441.     int flags;
  442.  
  443.     ret = regatom(&flags);
  444.     if (ret == NULL)
  445.         return(NULL);
  446.  
  447.     op = *regparse;
  448.     if (!ISMULT(op)) {
  449.         *flagp = flags;
  450.         return(ret);
  451.     }
  452.  
  453.     if (!(flags&HASWIDTH) && op != '?')
  454.         FAIL("*+ operand could be empty");
  455.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  456.  
  457.     if (op == '*' && (flags&SIMPLE))
  458.         reginsert(STAR, ret);
  459.     else if (op == '*') {
  460.         /* Emit x* as (x&|), where & means "self". */
  461.         reginsert(BRANCH, ret);            /* Either x */
  462.         regoptail(ret, regnode(BACK));        /* and loop */
  463.         regoptail(ret, ret);            /* back */
  464.         regtail(ret, regnode(BRANCH));        /* or */
  465.         regtail(ret, regnode(NOTHING));        /* null. */
  466.     } else if (op == '+' && (flags&SIMPLE))
  467.         reginsert(PLUS, ret);
  468.     else if (op == '+') {
  469.         /* Emit x+ as x(&|), where & means "self". */
  470.         next = regnode(BRANCH);            /* Either */
  471.         regtail(ret, next);
  472.         regtail(regnode(BACK), ret);        /* loop back */
  473.         regtail(next, regnode(BRANCH));        /* or */
  474.         regtail(ret, regnode(NOTHING));        /* null. */
  475.     } else if (op == '?') {
  476.         /* Emit x? as (x|) */
  477.         reginsert(BRANCH, ret);            /* Either x */
  478.         regtail(ret, regnode(BRANCH));        /* or */
  479.         next = regnode(NOTHING);        /* null. */
  480.         regtail(ret, next);
  481.         regoptail(ret, next);
  482.     }
  483.     regparse++;
  484.     if (ISMULT(*regparse))
  485.         FAIL("nested *?+");
  486.  
  487.     return(ret);
  488. }
  489.  
  490. /*
  491.  - regatom - the lowest level
  492.  *
  493.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  494.  * it can turn them into a single node, which is smaller to store and
  495.  * faster to run.  Backslashed characters are exceptions, each becoming a
  496.  * separate node; the code is simpler that way and it's not worth fixing.
  497.  */
  498. STATIC char *
  499. #if __STDC__
  500. regatom (int *flagp)
  501. #else
  502. regatom(flagp)
  503. int *flagp;
  504. #endif
  505. {
  506.     register char *ret;
  507.     int flags;
  508.  
  509.     *flagp = WORST;        /* Tentatively. */
  510.  
  511.     switch (*regparse++) {
  512.     case '^':
  513.         ret = regnode(BOL);
  514.         break;
  515.     case '$':
  516.         ret = regnode(EOL);
  517.         break;
  518.     case '.':
  519.         ret = regnode(ANY);
  520.         *flagp |= HASWIDTH|SIMPLE;
  521.         break;
  522.     case '[': {
  523.             register int class;
  524.             register int classend;
  525.  
  526.             if (*regparse == '^') {    /* Complement of range. */
  527.                 ret = regnode(ANYBUT);
  528.                 regparse++;
  529.             } else
  530.                 ret = regnode(ANYOF);
  531.             if (*regparse == ']' || *regparse == '-')
  532.                 regc(*regparse++);
  533.             while (*regparse != '\0' && *regparse != ']') {
  534.                 if (*regparse == '-') {
  535.                     regparse++;
  536.                     if (*regparse == ']' || *regparse == '\0')
  537.                         regc('-');
  538.                     else {
  539.                         class = UCHARAT(regparse-2)+1;
  540.                         classend = UCHARAT(regparse);
  541.                         if (class > classend+1)
  542.                             FAIL("invalid [] range");
  543.                         for (; class <= classend; class++)
  544.                             regc((char) class);
  545.                         regparse++;
  546.                     }
  547.                 } else
  548.                     regc(*regparse++);
  549.             }
  550.             regc('\0');
  551.             if (*regparse != ']')
  552.                 FAIL("unmatched []");
  553.             regparse++;
  554.             *flagp |= HASWIDTH|SIMPLE;
  555.         }
  556.         break;
  557.     case '(':
  558.         ret = reg(1, &flags);
  559.         if (ret == NULL)
  560.             return(NULL);
  561.         *flagp |= flags&(HASWIDTH|SPSTART);
  562.         break;
  563.     case '\0':
  564.     case '|':
  565.     case ')':
  566.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  567.         break;
  568.     case '?':
  569.     case '+':
  570.     case '*':
  571.         FAIL("?+* follows nothing");
  572.         break;
  573.     case '\\':
  574.         if (*regparse == '\0')
  575.             FAIL("trailing \\");
  576.         ret = regnode(EXACTLY);
  577.         regc(*regparse++);
  578.         regc('\0');
  579.         *flagp |= HASWIDTH|SIMPLE;
  580.         break;
  581.     default: {
  582.             register int len;
  583.             register char ender;
  584.  
  585.             regparse--;
  586.             len = strcspn(regparse, META);
  587.             if (len <= 0)
  588.                 FAIL("internal disaster");
  589.             ender = *(regparse+len);
  590.             if (len > 1 && ISMULT(ender))
  591.                 len--;        /* Back off clear of ?+* operand. */
  592.             *flagp |= HASWIDTH;
  593.             if (len == 1)
  594.                 *flagp |= SIMPLE;
  595.             ret = regnode(EXACTLY);
  596.             while (len > 0) {
  597.                 regc(*regparse++);
  598.                 len--;
  599.             }
  600.             regc('\0');
  601.         }
  602.         break;
  603.     }
  604.  
  605.     return(ret);
  606. }
  607.  
  608. /*
  609.  - regnode - emit a node
  610.  */
  611. STATIC char *            /* Location. */
  612. #if __STDC__
  613. regnode (char op)
  614. #else
  615. regnode(op)
  616. char op;
  617. #endif
  618. {
  619.     register char *ret;
  620.     register char *ptr;
  621.  
  622.     ret = regcode;
  623.     if (ret == ®dummy) {
  624.         regsize += 3;
  625.         return(ret);
  626.     }
  627.  
  628.     ptr = ret;
  629.     *ptr++ = op;
  630.     *ptr++ = '\0';        /* Null "next" pointer. */
  631.     *ptr++ = '\0';
  632.     regcode = ptr;
  633.  
  634.     return(ret);
  635. }
  636.  
  637. /*
  638.  - regc - emit (if appropriate) a byte of code
  639.  */
  640. STATIC void
  641. #if __STDC__
  642. regc (char b)
  643. #else
  644. regc(b)
  645. char b;
  646. #endif
  647. {
  648.     if (regcode != ®dummy)
  649.         *regcode++ = b;
  650.     else
  651.         regsize++;
  652. }
  653.  
  654. /*
  655.  - reginsert - insert an operator in front of already-emitted operand
  656.  *
  657.  * Means relocating the operand.
  658.  */
  659. STATIC void
  660. #if __STDC__
  661. reginsert (char op, char *opnd)
  662. #else
  663. reginsert(op, opnd)
  664. char op;
  665. char *opnd;
  666. #endif
  667. {
  668.     register char *src;
  669.     register char *dst;
  670.     register char *place;
  671.  
  672.     if (regcode == ®dummy) {
  673.         regsize += 3;
  674.         return;
  675.     }
  676.  
  677.     src = regcode;
  678.     regcode += 3;
  679.     dst = regcode;
  680.     while (src > opnd)
  681.         *--dst = *--src;
  682.  
  683.     place = opnd;        /* Op node, where operand used to be. */
  684.     *place++ = op;
  685.     *place++ = '\0';
  686.     *place++ = '\0';
  687. }
  688.  
  689. /*
  690.  - regtail - set the next-pointer at the end of a node chain
  691.  */
  692. STATIC void
  693. #if __STDC__
  694. regtail (char *p, char *val)
  695. #else
  696. regtail(p, val)
  697. char *p;
  698. char *val;
  699. #endif
  700. {
  701.     register char *scan;
  702.     register char *temp;
  703.     register int offset;
  704.  
  705.     if (p == ®dummy)
  706.         return;
  707.  
  708.     /* Find last node. */
  709.     scan = p;
  710.     for (;;) {
  711.         temp = regnext(scan);
  712.         if (temp == NULL)
  713.             break;
  714.         scan = temp;
  715.     }
  716.  
  717.     if (OP(scan) == BACK)
  718.         offset = scan - val;
  719.     else
  720.         offset = val - scan;
  721.     *(scan+1) = (char) ((offset>>8)&0377);
  722.     *(scan+2) = (char) (offset&0377);
  723. }
  724.  
  725. /*
  726.  - regoptail - regtail on operand of first argument; nop if operandless
  727.  */
  728. STATIC void
  729. #if __STDC__
  730. regoptail (char *p, char *val)
  731. #else
  732. regoptail(p, val)
  733. char *p;
  734. char *val;
  735. #endif
  736. {
  737.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  738.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  739.         return;
  740.     regtail(OPERAND(p), val);
  741. }
  742.  
  743. /*
  744.  * regexec and friends
  745.  */
  746.  
  747. /*
  748.  * Global work variables for regexec().
  749.  */
  750. static char *reginput;        /* String-input pointer. */
  751. static char *regbol;        /* Beginning of input, for ^ check. */
  752. static char **regstartp;    /* Pointer to startp array. */
  753. static char **regendp;        /* Ditto for endp. */
  754.  
  755. /*
  756.  * Forwards.
  757.  */
  758. #if __STDC__
  759. STATIC int regtry (regexp *, char *);
  760. STATIC int regmatch (char *);
  761. STATIC int regrepeat (char *);
  762. #else
  763. STATIC int regtry();
  764. STATIC int regmatch();
  765. STATIC int regrepeat();
  766. #endif
  767.  
  768. #ifdef DEBUG
  769. int regnarrate = 0;
  770. # if __STDC__
  771. void regdump (const regexp *);
  772. STATIC char *regprop (const char *);
  773. # else
  774. void regdump();
  775. STATIC char *regprop();
  776. # endif
  777. #endif
  778.  
  779. /*
  780.  - regexec - match a regexp against a string
  781.  */
  782. int
  783. #if __STDC__
  784. regexec (register regexp *prog, register char *string)
  785. #else
  786. regexec(prog, string)
  787. register regexp *prog;
  788. register char *string;
  789. #endif
  790. {
  791.     register char *s;
  792. #if !__STDC__
  793.     extern char *strchr();
  794. #endif
  795.  
  796.     /* Be paranoid... */
  797.     if (prog == NULL || string == NULL) {
  798.         regerror("NULL parameter");
  799.         return(0);
  800.     }
  801.  
  802.     /* Check validity of program. */
  803.     if (UCHARAT(prog->program) != MAGIC) {
  804.         regerror("corrupted program");
  805.         return(0);
  806.     }
  807.  
  808.     /* If there is a "must appear" string, look for it. */
  809.     if (prog->regmust != NULL) {
  810.         s = string;
  811.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  812.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  813.                 break;    /* Found it. */
  814.             s++;
  815.         }
  816.         if (s == NULL)    /* Not present. */
  817.             return(0);
  818.     }
  819.  
  820.     /* Mark beginning of line for ^ . */
  821.     regbol = string;
  822.  
  823.     /* Simplest case:  anchored match need be tried only once. */
  824.     if (prog->reganch)
  825.         return(regtry(prog, string));
  826.  
  827.     /* Messy cases:  unanchored match. */
  828.     s = string;
  829.     if (prog->regstart != '\0')
  830.         /* We know what char it must start with. */
  831.         while ((s = strchr(s, prog->regstart)) != NULL) {
  832.             if (regtry(prog, s))
  833.                 return(1);
  834.             s++;
  835.         }
  836.     else
  837.         /* We don't -- general case. */
  838.         do {
  839.             if (regtry(prog, s))
  840.                 return(1);
  841.         } while (*s++ != '\0');
  842.  
  843.     /* Failure. */
  844.     return(0);
  845. }
  846.  
  847. /*
  848.  - regtry - try match at specific point
  849.  */
  850. STATIC int            /* 0 failure, 1 success */
  851. #if __STDC__
  852. regtry (regexp *prog, char *string)
  853. #else
  854. regtry(prog, string)
  855. regexp *prog;
  856. char *string;
  857. #endif
  858. {
  859.     register int i;
  860.     register char **sp;
  861.     register char **ep;
  862.  
  863.     reginput = string;
  864.     regstartp = prog->startp;
  865.     regendp = prog->endp;
  866.  
  867.     sp = prog->startp;
  868.     ep = prog->endp;
  869.     for (i = NSUBEXP; i > 0; i--) {
  870.         *sp++ = NULL;
  871.         *ep++ = NULL;
  872.     }
  873.     if (regmatch(prog->program + 1)) {
  874.         prog->startp[0] = string;
  875.         prog->endp[0] = reginput;
  876.         return(1);
  877.     } else
  878.         return(0);
  879. }
  880.  
  881. /*
  882.  - regmatch - main matching routine
  883.  *
  884.  * Conceptually the strategy is simple:  check to see whether the current
  885.  * node matches, call self recursively to see whether the rest matches,
  886.  * and then act accordingly.  In practice we make some effort to avoid
  887.  * recursion, in particular by going through "ordinary" nodes (that don't
  888.  * need to know whether the rest of the match failed) by a loop instead of
  889.  * by recursion.
  890.  */
  891. STATIC int            /* 0 failure, 1 success */
  892. #if __STDC__
  893. regmatch (char *prog)
  894. #else
  895. regmatch(prog)
  896. char *prog;
  897. #endif
  898. {
  899.     register char *scan;    /* Current node. */
  900.     char *next;        /* Next node. */
  901. #if !__STDC__
  902.     extern char *strchr();
  903. #endif
  904.  
  905.     scan = prog;
  906. #ifdef DEBUG
  907.     if (scan != NULL && regnarrate)
  908.         fprintf(stderr, "%s(\n", regprop(scan));
  909. #endif
  910.     while (scan != NULL) {
  911. #ifdef DEBUG
  912.         if (regnarrate)
  913.             fprintf(stderr, "%s...\n", regprop(scan));
  914. #endif
  915.         next = regnext(scan);
  916.  
  917.         switch (OP(scan)) {
  918.         case BOL:
  919.             if (reginput != regbol)
  920.                 return(0);
  921.             break;
  922.         case EOL:
  923.             if (*reginput != '\0')
  924.                 return(0);
  925.             break;
  926.         case ANY:
  927.             if (*reginput == '\0')
  928.                 return(0);
  929.             reginput++;
  930.             break;
  931.         case EXACTLY: {
  932.                 register int len;
  933.                 register char *opnd;
  934.  
  935.                 opnd = OPERAND(scan);
  936.                 /* Inline the first character, for speed. */
  937.                 if (*opnd != *reginput)
  938.                     return(0);
  939.                 len = strlen(opnd);
  940.                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  941.                     return(0);
  942.                 reginput += len;
  943.             }
  944.             break;
  945.         case ANYOF:
  946.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  947.                 return(0);
  948.             reginput++;
  949.             break;
  950.         case ANYBUT:
  951.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  952.                 return(0);
  953.             reginput++;
  954.             break;
  955.         case NOTHING:
  956.             break;
  957.         case BACK:
  958.             break;
  959.         case OPEN+1:
  960.         case OPEN+2:
  961.         case OPEN+3:
  962.         case OPEN+4:
  963.         case OPEN+5:
  964.         case OPEN+6:
  965.         case OPEN+7:
  966.         case OPEN+8:
  967.         case OPEN+9: {
  968.                 register int no;
  969.                 register char *save;
  970.  
  971.                 no = OP(scan) - OPEN;
  972.                 save = reginput;
  973.  
  974.                 if (regmatch(next)) {
  975.                     /*
  976.                      * Don't set startp if some later
  977.                      * invocation of the same parentheses
  978.                      * already has.
  979.                      */
  980.                     if (regstartp[no] == NULL)
  981.                         regstartp[no] = save;
  982.                     return(1);
  983.                 } else
  984.                     return(0);
  985.             }
  986.             break;
  987.         case CLOSE+1:
  988.         case CLOSE+2:
  989.         case CLOSE+3:
  990.         case CLOSE+4:
  991.         case CLOSE+5:
  992.         case CLOSE+6:
  993.         case CLOSE+7:
  994.         case CLOSE+8:
  995.         case CLOSE+9: {
  996.                 register int no;
  997.                 register char *save;
  998.  
  999.                 no = OP(scan) - CLOSE;
  1000.                 save = reginput;
  1001.  
  1002.                 if (regmatch(next)) {
  1003.                     /*
  1004.                      * Don't set endp if some later
  1005.                      * invocation of the same parentheses
  1006.                      * already has.
  1007.                      */
  1008.                     if (regendp[no] == NULL)
  1009.                         regendp[no] = save;
  1010.                     return(1);
  1011.                 } else
  1012.                     return(0);
  1013.             }
  1014.             break;
  1015.         case BRANCH: {
  1016.                 register char *save;
  1017.  
  1018.                 if (OP(next) != BRANCH)        /* No choice. */
  1019.                     next = OPERAND(scan);    /* Avoid recursion. */
  1020.                 else {
  1021.                     do {
  1022.                         save = reginput;
  1023.                         if (regmatch(OPERAND(scan)))
  1024.                             return(1);
  1025.                         reginput = save;
  1026.                         scan = regnext(scan);
  1027.                     } while (scan != NULL && OP(scan) == BRANCH);
  1028.                     return(0);
  1029.                     /* NOTREACHED */
  1030.                 }
  1031.             }
  1032.             break;
  1033.         case STAR:
  1034.         case PLUS: {
  1035.                 register char nextch;
  1036.                 register int no;
  1037.                 register char *save;
  1038.                 register int min;
  1039.  
  1040.                 /*
  1041.                  * Lookahead to avoid useless match attempts
  1042.                  * when we know what character comes next.
  1043.                  */
  1044.                 nextch = '\0';
  1045.                 if (OP(next) == EXACTLY)
  1046.                     nextch = *OPERAND(next);
  1047.                 min = (OP(scan) == STAR) ? 0 : 1;
  1048.                 save = reginput;
  1049.                 no = regrepeat(OPERAND(scan));
  1050.                 while (no >= min) {
  1051.                     /* If it could work, try it. */
  1052.                     if (nextch == '\0' || *reginput == nextch)
  1053.                         if (regmatch(next))
  1054.                             return(1);
  1055.                     /* Couldn't or didn't -- back up. */
  1056.                     no--;
  1057.                     reginput = save + no;
  1058.                 }
  1059.                 return(0);
  1060.             }
  1061.             break;
  1062.         case END:
  1063.             return(1);    /* Success! */
  1064.             break;
  1065.         default:
  1066.             regerror("memory corruption");
  1067.             return(0);
  1068.             break;
  1069.         }
  1070.  
  1071.         scan = next;
  1072.     }
  1073.  
  1074.     /*
  1075.      * We get here only if there's trouble -- normally "case END" is
  1076.      * the terminating point.
  1077.      */
  1078.     regerror("corrupted pointers");
  1079.     return(0);
  1080. }
  1081.  
  1082. /*
  1083.  - regrepeat - repeatedly match something simple, report how many
  1084.  */
  1085. STATIC int
  1086. #if __STDC__
  1087. regrepeat (char *p)
  1088. #else
  1089. regrepeat(p)
  1090. char *p;
  1091. #endif
  1092. {
  1093.     register int count = 0;
  1094.     register char *scan;
  1095.     register char *opnd;
  1096.  
  1097.     scan = reginput;
  1098.     opnd = OPERAND(p);
  1099.     switch (OP(p)) {
  1100.     case ANY:
  1101.         count = strlen(scan);
  1102.         scan += count;
  1103.         break;
  1104.     case EXACTLY:
  1105.         while (*opnd == *scan) {
  1106.             count++;
  1107.             scan++;
  1108.         }
  1109.         break;
  1110.     case ANYOF:
  1111.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1112.             count++;
  1113.             scan++;
  1114.         }
  1115.         break;
  1116.     case ANYBUT:
  1117.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1118.             count++;
  1119.             scan++;
  1120.         }
  1121.         break;
  1122.     default:        /* Oh dear.  Called inappropriately. */
  1123.         regerror("internal foulup");
  1124.         count = 0;    /* Best compromise. */
  1125.         break;
  1126.     }
  1127.     reginput = scan;
  1128.  
  1129.     return(count);
  1130. }
  1131.  
  1132. /*
  1133.  - regnext - dig the "next" pointer out of a node
  1134.  */
  1135. STATIC char *
  1136. #if __STDC__
  1137. regnext (register char *p)
  1138. #else
  1139. regnext(p)
  1140. register char *p;
  1141. #endif
  1142. {
  1143.     register int offset;
  1144.  
  1145.     if (p == ®dummy)
  1146.         return(NULL);
  1147.  
  1148.     offset = NEXT(p);
  1149.     if (offset == 0)
  1150.         return(NULL);
  1151.  
  1152.     if (OP(p) == BACK)
  1153.         return(p-offset);
  1154.     else
  1155.         return(p+offset);
  1156. }
  1157.  
  1158. #ifdef DEBUG
  1159.  
  1160. #if 0
  1161. STATIC char *regprop();
  1162. #endif
  1163.  
  1164. /*
  1165.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1166.  */
  1167. void
  1168. #if __STDC__
  1169. regdump (const regexp *r)
  1170. #else
  1171. regdump(r)
  1172. regexp *r;
  1173. #endif
  1174. {
  1175.     register char *s;
  1176.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1177.     register char *next;
  1178. #if !__STDC__
  1179.     extern char *strchr();
  1180. #endif
  1181.  
  1182.     s = r->program + 1;
  1183.     while (op != END) {    /* While that wasn't END last time... */
  1184.         op = OP(s);
  1185.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1186.         next = regnext(s);
  1187.         if (next == NULL)        /* Next ptr. */
  1188.             printf("(0)");
  1189.         else 
  1190.             printf("(%d)", (s-r->program)+(next-s));
  1191.         s += 3;
  1192.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1193.             /* Literal string, where present. */
  1194.             while (*s != '\0') {
  1195.                 putchar(*s);
  1196.                 s++;
  1197.             }
  1198.             s++;
  1199.         }
  1200.         putchar('\n');
  1201.     }
  1202.  
  1203.     /* Header fields of interest. */
  1204.     if (r->regstart != '\0')
  1205.         printf("start `%c' ", r->regstart);
  1206.     if (r->reganch)
  1207.         printf("anchored ");
  1208.     if (r->regmust != NULL)
  1209.         printf("must have \"%s\"", r->regmust);
  1210.     printf("\n");
  1211. }
  1212.  
  1213. /*
  1214.  - regprop - printable representation of opcode
  1215.  */
  1216. STATIC char *
  1217. #if __STDC__
  1218. regprop (const char *op)
  1219. #else
  1220. regprop(op)
  1221. char *op;
  1222. #endif
  1223. {
  1224.     register char *p;
  1225.     static char buf[50];
  1226.  
  1227.     (void) strcpy(buf, ":");
  1228.  
  1229.     switch (OP(op)) {
  1230.     case BOL:
  1231.         p = "BOL";
  1232.         break;
  1233.     case EOL:
  1234.         p = "EOL";
  1235.         break;
  1236.     case ANY:
  1237.         p = "ANY";
  1238.         break;
  1239.     case ANYOF:
  1240.         p = "ANYOF";
  1241.         break;
  1242.     case ANYBUT:
  1243.         p = "ANYBUT";
  1244.         break;
  1245.     case BRANCH:
  1246.         p = "BRANCH";
  1247.         break;
  1248.     case EXACTLY:
  1249.         p = "EXACTLY";
  1250.         break;
  1251.     case NOTHING:
  1252.         p = "NOTHING";
  1253.         break;
  1254.     case BACK:
  1255.         p = "BACK";
  1256.         break;
  1257.     case END:
  1258.         p = "END";
  1259.         break;
  1260.     case OPEN+1:
  1261.     case OPEN+2:
  1262.     case OPEN+3:
  1263.     case OPEN+4:
  1264.     case OPEN+5:
  1265.     case OPEN+6:
  1266.     case OPEN+7:
  1267.     case OPEN+8:
  1268.     case OPEN+9:
  1269.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1270.         p = NULL;
  1271.         break;
  1272.     case CLOSE+1:
  1273.     case CLOSE+2:
  1274.     case CLOSE+3:
  1275.     case CLOSE+4:
  1276.     case CLOSE+5:
  1277.     case CLOSE+6:
  1278.     case CLOSE+7:
  1279.     case CLOSE+8:
  1280.     case CLOSE+9:
  1281.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1282.         p = NULL;
  1283.         break;
  1284.     case STAR:
  1285.         p = "STAR";
  1286.         break;
  1287.     case PLUS:
  1288.         p = "PLUS";
  1289.         break;
  1290.     default:
  1291.         regerror("corrupted opcode");
  1292.         break;
  1293.     }
  1294.     if (p != NULL)
  1295.         (void) strcat(buf, p);
  1296.     return(buf);
  1297. }
  1298. #endif
  1299.  
  1300. /*
  1301.  * The following is provided for those people who do not have strcspn() in
  1302.  * their C libraries.  They should get off their butts and do something
  1303.  * about it; at least one public-domain implementation of those (highly
  1304.  * useful) string routines has been published on Usenet.
  1305.  */
  1306. #ifdef STRCSPN
  1307. /*
  1308.  * strcspn - find length of initial segment of s1 consisting entirely
  1309.  * of characters not from s2
  1310.  */
  1311.  
  1312. static int
  1313. strcspn(s1, s2)
  1314. char *s1;
  1315. char *s2;
  1316. {
  1317.     register char *scan1;
  1318.     register char *scan2;
  1319.     register int count;
  1320.  
  1321.     count = 0;
  1322.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1323.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1324.             if (*scan1 == *scan2++)
  1325.                 return(count);
  1326.         count++;
  1327.     }
  1328.     return(count);
  1329. }
  1330. #endif
  1331.